The present invention relates to data processing, and more specifically, to physical design of an integrated circuit.
Physical design is the process of transforming a logical design of an integrated circuit, expressed, for example, in a register transfer level (RTL) or gate-level netlist description, into a physical realization of the integrated circuit. One of the first steps of physical design is global placement, which assigns modules in a netlist description to generally nonoverlapping locations within the fixed area allocated to an integrated circuit die. During global placement, a placement tool (or placer) is typically employed to generate an automatic placement of the modules with approximately regular module densities while optimizing some cost metric (typically wirelength).
Current placement algorithms include simulated annealing, min-cut, and analytical algorithms. Simulated annealing placement optimizes module placement by perturbing module positions based on simulated annealing. While good results can be obtained for small designs, simulated annealing placement lacks scalability and is therefore not applicable to large-scale circuit designs.
Min-cut placement recursively partitions the integrated circuit design and die area and assign sub-circuits of the integrated circuit design into sub-regions of the area. Min-cut placement is usually efficient and scalable and generally minimizes wirelength by minimizing the number of cuts between sub-circuits. However, by hierarchically partitioning the design and solving each partition independently, min-cut placers may reduce solution quality due to the omission of global information regarding the interaction among different circuit partitions. In addition, optimizing the cut value does not always directly translate to optimizing the wirelength of the design.
Analytical placement models placement as a mathematical programming problem composed of an objective function and a set of placement constraints. The analytical placement tool optimizes the objective function through analytical approaches, which generally achieve better placement quality for large-scale integrated circuit designs. Analytical placement commonly uses half-perimeter wirelength (HPWL) as the primary objective function because HPWL provides a good first order approximation of the routed wirelength that will eventually be achieved in the physical integrated circuit die.